330E - Graph Reconstruction - CodeForces Solution

#pragma GCC optimize("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <bitset>
#include <set>
#include <unordered_set>
#include <utility>
#include <numeric>
#include <iomanip>
#include <stack>
#include <list>
#include <bitset>
#include <sstream>
#define ll long long
#define ld long double
#define INF 0x3f3f3f3f
#define MXN 1000005
#define cl(x) (x << 1)
#define cr(x) ((x << 1) | 1)
#define SZ(x) (int)x.size()
#define PB push_back
#define lowbit(x) (x & (-x))
#define NO_TAG false
#define P1 75577
#define P2 12721
#define MOD1 998244353
#define MOD2 1000000007

using namespace std;

int n, m;

void solve(){
    cin >> n >> m;
    map<pair<int, int>, bool> mp;
    for (int i = 0, u, v; i < m; i++){
        cin >> u >> v;
        mp[{u, v}] = true;
        mp[{v, u}] = true;
    }
    vector<int> v(n);
    for (int i = 0; i < n; i++){
        v[i] = i + 1;
    }
    int t = 10005;
    bool hasAns = false;
    while (t--){
        random_shuffle(v.begin(), v.end());
        bool ok = true;
        for (int i = 0; i < n - 1; i++){
            if (mp[{v[i], v[i + 1]}]){
                ok = false;
                break;
            }
        }
        if (ok){
            hasAns = true;
            break;
        }
    }
    if (hasAns){
        vector<pair<int, int>> res;
        for (int i = 0; i < n; i++){
            res.push_back({v[i], v[(i + 1) % n]});
        }
        for (int i = 0; i < m; i++){
            cout << res[i].first << " " << res[i].second << "\n";
        }
        return ;
    }
    cout << "-1\n";
    return ;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--){
        solve();
    }
    return 0;
}